package top.jolyoulu.力扣._1053_交换一次的先前排列;
//给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于
//arr 的最大排列。
//
// 如果无法这么操作，就请返回原数组。
//
//
//
// 示例 1：
//
//
//输入：arr = [3,2,1]
//输出：[3,1,2]
//解释：交换 2 和 1
//
//
// 示例 2：
//
//
//输入：arr = [1,1,5]
//输出：[1,1,5]
//解释：已经是最小排列
//
//
// 示例 3：
//
//
//输入：arr = [1,9,4,6,7]
//输出：[1,7,4,6,9]
//解释：交换 9 和 7
//
//
//
//
// 提示：
//
//
// 1 <= arr.length <= 10⁴
// 1 <= arr[i] <= 10⁴
//
//
// Related Topics 贪心 数组 👍 83 👎 0


import top.jolyoulu.utils.TimerUtils;

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
public class Answer1 {
    /*
        思路：
        正常情况下右往左是依次递减的，所有从右边i开始找数据，找到i > i+1的位置，表示需要替换的位置
        从a[i]开始，往右边找找到最大数据去除来，和a[i]替换，那么就可以解题
    */
    class Solution {
        public int[] prevPermOpt1(int[] arr) {
            for (int i = arr.length - 2; i >= 0; i--) {
                int max = -1;
                if (arr[i] > arr[i + 1]) {
                    for (int j = i; j < arr.length; j++) {
                        if (arr[i] > arr[j] && (max == -1 || arr[j] > arr[max])) {
                            max = j;
                        }
                    }
                }
                if (max != -1) {
                    int tmp = arr[max];
                    arr[max] = arr[i];
                    arr[i] = tmp;
                    break;
                }
            }
            return arr;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Answer1().new Solution();
        System.out.println("用例1=======================================");
        System.out.println("arr = {3,2,1}");
        int[] arr1 = {3, 2, 1};
        TimerUtils.timer(() -> {
            solution.prevPermOpt1(arr1);
        });
        System.out.println(Arrays.toString(arr1));
        System.out.println("用例2=======================================");
        System.out.println("arr = {1,9,4,6,7}");
        int[] arr2 = {1, 9, 4, 6, 7};
        TimerUtils.timer(() -> {
            solution.prevPermOpt1(arr2);
        });
        System.out.println(Arrays.toString(arr2));
        System.out.println("用例3=======================================");
        System.out.println("arr = {1,1,5}");
        int[] arr3 = {1, 1, 5};
        TimerUtils.timer(() -> {
            solution.prevPermOpt1(arr3);
        });
        System.out.println(Arrays.toString(arr3));
        System.out.println("用例4=======================================");
        System.out.println("arr = {8,9,5,7,2,4}");
        int[] arr4 = {8, 9, 5, 7, 2, 4};
        TimerUtils.timer(() -> {
            solution.prevPermOpt1(arr4);
        });
        System.out.println(Arrays.toString(arr4));
    }
}
//leetcode submit region end(Prohibit modification and deletion)